import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class project {
    public int[][] matrixBlockSum(int[][] mat, int k) {
         int row=mat.length;
         int col=mat[0].length;
         int[][] dp=new int[row+1][col+1];
         int[][] ret=new int[row][col];
         for(int i=1;i<=row;i++){
             for(int j=1;j<=col;j++){
                 dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+mat[i-1][j-1];
             }
         }
         for(int i=0;i<row;i++){
             for(int j=0;j<col;j++){
                 int upX=Math.min(i+k+1,row);
                 int upY=Math.min(j+k+1,col);
                 int x=Math.max(i-k,0);
                 int y=Math.max(j-k,0);
                 ret[i][j]=dp[upX][upY]-dp[upX][y]-dp[x][upY]+dp[x][y];
             }
         }
         return ret;
    }



















    public int countPrefixes(String[] words, String s) {
        int ret=0;
        for(String word:words){
            int size=word.length();
            if(size<=s.length()&&s.substring(0,size).equals(word)){
                ret++;
            }
        }
        return ret;
    }















    List<Integer> list=new ArrayList<>();
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        dfs(root1);
        dfs(root2);
        Collections.sort(list);
        return list;
    }
    public void dfs(TreeNode root){
        if(root==null){
            return;
        }
        list.add(root.val);
        dfs(root.left);
        dfs(root.right);
    }
}
